目录

一、前言

二、LinkedList类简介

三、LinkedList类的底层实现

四、LinkedList  VS ArrayList

        1.如何抉择 : 

        2.比较图 :   

五、LinkedList类的源码解读

        1.add方法解读 : 

                〇准备工作 。

                ①跳入无参构造。

                ②跳入add方法。

                ③跳入linkList方法。

                ④增加第一个元素成功。

                ⑤向链表中添加第二个元素。

        2.remove方法解读 : 

                〇准备工作 。

                ①关于LinkedList类的remove方法。                                

                ②跳入remove() 方法。

                ③跳入removeFirst() 方法。

                ④跳入unlinkFirst() 方法。

                ⑤第一个元素被除去。                

六、总结

        大家好，今天给大家带来的是LinkedList类的内容分享。对于单列集合List的三个最常用的实现类——ArrayList, Vector, LinkedList，在前面的小节中，我们已经进行了ArrayList类和Vector类的源码解读。但对于List接口的第三大实现类LinkedList，由于其底层涉及了较多数据结构与算法的知识，而本篇博文主要面向过渡阶段，因此up准备简单给大家过一下，把LinkedList的底层机制搞明白就好，大家可放心食用，更多内容up准备在将来的java---《数据结构与算法》专栏再拓展。

        注意 : ① 解读源码需要扎实的基础，比较适合希望深究的同学； ② 不要眼高手低，自己跟着过一遍才真正有收获。 ③ 点击侧边栏目录或者文章开头的目录可以跳转。良工不示人以朴，所有文章都会适时改进。 感谢阅读！

        1.LinkedList是一种常见的线性表，每一个结点中都存放了下一个结点的地址。LinkedList类属于java.base模块，java.util包下，如下图所示 : 

        我们再来看看LinkedList 类的类图，如下所示 : 

        2.链表又分为单向链表和双向链表。一个单向链表包含两个值——当前结点的值和下一个结点的地址值(以指向后一个结点)；一个双向链表包含三个值——前一个结点的地址值(以指向前一个结点)，当前结点的值和下一个结点的地址值(以指向后一个结点)。

        3.LinkedList底层实现了双向链表和双端队列的特点。

        4.同ArrayList类似，可以向LinkedList集合中添加任意元素，包括null，并且元素允许重复。

        5.同ArrayList一样，LinkedList也没有实现线程同步，因此LinkedList线程不安全。

        1.LinkedList的底层维护了一个双向链表。在IDEA的类图中，我们查看LinkedList类的字段可以发现，LinkedList类中维护了两个属性first和last，见名知意，它们分别指向双向链表的首结点和尾结点。我们也可以在源码中找到first 和 last，如下图所示 : 

        2.每个结点（Node对象）中又维护了prev，next，item，三个属性，其中通过prev指向前一个结点，通过next指向后一个结点，从而实现双向链表。此处的Node类型，实际上是LinkedList中维护的一个静态内部类，如下图所示 : 

        3.LinkedList中元素的添加和删除，在底层不是通过数组来完成的，而是通过链表来完成的，因此LinkedList相对来说增删的效率更高。        PS :          以上内容涉及到了数据结构基础中关于链表的部分知识（比如什么是首结点和尾结点），当然，仅仅是涉及到一些基础的概念性的知识，若实在无法理解，可先去学习“数据结构与算法”这门课程。        双向链表的示意图如下 : (注意箭头是指向结点整体)

        这里up用java来模拟一个简单的双向链表，现在我们想创建三个璃月人对象——刻晴，甘雨，钟离，并且让它们形成如下的双向链表关系：

         以Link_Simulation类为例，代码如下 : (自己模拟一个Node类)

        运行结果 : 

        ①增删操作多，优先选择LinkedList；改查操作多，优先选择ArrayList。

        ②实际开发中，往往对集合的改查操作比较多，因此ArrayList一般用的较多。

        ③有时候一个项目的不同模块会使用不同的选择。（根据实际业务需求来选择）

        ④ArrayList与LinkedList 线程均不安全，建议单线程情况下使用。

                up以LinkedList_Demo1为演示类，代码如下 :（在创建对象那行代码设置断点）

                如下图所示 : 

                可以看到，LinkedList类的无参构造其实是什么也没有做，因为它底层使用链表实现的，所以不需要创建数组。我们跳出无参构造。无参构造器执行完毕后，我们可以看到LinkedList对象已经初始化完毕(LinkedList维护的first属性和last属性经过了默认初始化-->显式初始化--构造器初始化，最后仍为默认值)，如下图所示 :

                注意看，此时 first 和 last 均为null类型。所以，链表此时是这样一个效果 : 

                如下图所示 :                 

                因为我们要向链表中添加的元素为int类型，所以第一次跳入add方法是一个自动装箱的过程，我们不用管他，直接跳出。

                再次跳入add方法，如下图所示 : 

                形参列表的"E e"表示我们当前要添加的元素，所以此时e = 11。add方法中调用了linkLast方法，不用想也能猜到，这个linkLast方法里面完成了添加元素的操作，我们继续追进去看看，如下图所示 : 

                我们一步一步来看——                 首先, Node是“结点”的意思，就是Node类型。                  其次，还记得我们上面提到说——first 和 last此时均为null。所以，linkLast方法内，第一步是定义了一个Node类型的常指针l，并令其指向为last（即null）；                 接着，又定义了一个Node类型的常量newNode，见名知意，"newNode"就是我们要添加的新结点。那么，为newNode初始化的这个带参构造是怎么执行的呢？这三个实参分别是干嘛的？别急，我们这就通过Ctrl + b/B快捷键，追到其源码中看看，如下图所示 : 

                一看源码我们就明白了，这不就是上文中我们提到的——双向链表的三个值吗？所以，对应此处的三个实参，l就是prev，此时为null；e就是已经装箱好的11；null就是next的值。因此，newNode引用此时指向的就是一个前后均为空，值为11的新结点。并且，之后又令last指向了该新结点。         

                继续向下执行，是一个if-else的复合条件语句。判断条件"l == null"显然满足，令first也指向了该新结点；之后，又令size自增1（size表示当前链表中元素的个数），modCount也自增1（修改次数)。

                好的，linkList方法执行完毕后，此时链表就长下面这样子 : 

                接下来，我们逐层跳出，直到演示类中。我们可以看到此时链表的状态，如下图所示 : 

                可以看到，first 和 last 都指向了同一个结点，并且该结点中prev和next均为null。

                向链表中添加第二个元素，由于前面几个步骤都一样，我们就不再赘述了，直接从linkList方法开始说起，如下 : 

                还是一步一步来看——                 首先，令Node类型的常指针l 指向了last所指向的结点(即我们刚刚添加的第一个结点，此时也为链表中的最后一个结点）。                  其次，第二个新结点进行初始化工作。注意，第一个实参l 代表的是新结点的prev，而l 此时又指向了第一个结点，因此，这一步实现了——令新节点的prev指向了第一个结点。                 接着，又令last指向了新结点（此时first仍指向第一个结点）。                 然后，就是if-else的判断语句了，因为l 已经指向了刚刚添加好的第一个结点，不为空，所以执行ele中的语句，令第一个结点的next指向了新结点。                 最后，就是size和modCount的自增。

                所以，第二次linkList方法执行完毕后，链表就应该长下面这个样子 : 

                up以LinkedList_Demo2为演示类，代码如下 :（在remove方法那行代码设置断点）

                运行结果 : 

                如代码所示，我们事先在链表中加入三个元素：11，141，5。则在删除元素之前，我们的双向链表应该长下面这样子 : 

                通过查看API文档，我们可得知LinkedList类的remove有三个重载方法，如下图所示 : 

                其中，形参列表为空的remove() 方法，其内部默认调用的是removeFrist方法，即默认删去链表中的第一个元素；形参列表需要传入一个索引的remove(int index) 方法，可以删去链表中指定索引位置的元素，较复杂；形参列表需要传入一个Object类型的值的remove(Object o)方法，是删去链表中与该值匹配的第一个元素。                 up就以最简单的remove() 方法，通过Debug，来给大家分析一下。

                我们直接在remove方法的调用行设置断点跳过去，并跳入remove方法，如下图所示 : 

                可以看到，果然是调用了removeFirst() 方法，那它底层到底是如何把链表的第一个元素给干掉的？我们继续往里面追，如下图所示 : 

                removeFirst方法内部还是比较简洁的。                 首先，它令一个Node类型的常指针f 指向了首结点（即第一个存放有效数据的结点），然后判断首结点是否为空。由于我们一开始就在链表中添加了3个元素，所以此处f 肯定不为空。因此，if语句中的内容会跳过，return一个unlinkFirst() 方法的返回值。       

                可以看到，removeFirst方法内部并没有执行删除操作的代码。我们继续追入unlinkFirst方法，如下图所示 : 

                哎呀我趣，看这一大串，显然删除操作是在这里面完成的。                  老规矩，我们一步一步来看——                 首先，第一条语句不用看。因为这只是在函数最后return的删除掉的元素的值，与删除过程本身无关。                 其次，第二条语句，它令一个Node类型的常指针next指向了"第一个结点的next属性所指向的"值，即指向了第二个结点，如下图所示 : 

                接着，又依次置空了第一个结点的item和next，并且令first 指向了第二个结点，如下图所示 : 

                继续， 由于next现在指向的是第二个结点，不为空，所以接下里要进入else语句中。else语句中，令第二个结点的prev为null，如下图所示 : 

                至此，第一个元素已经被干掉了。回忆一下案发现场，jvm先是破掉了第一个结点的"盾牌"（即first）；接着又切断了第一个结点的"逃跑路线"(即next），最后又斩断了第一个结点的"后援"（即第二个结点的prev）。那第一个结点手无寸铁，又成了单兵作战，留给它的命运只能是被gc垃圾回收器除去，哎，可悲。（bushi）

         🆗，以上就是关于LinkedList源码分析的全部内容了。由于LinkedList作为以链表为实现基础的容器，涉及到较多数据结构与算法的内容。因此本篇博文中up也是尽量"避重就轻"，已不至于晦涩。当然，对于有些在学C语言的时候接触过链表的小伙伴儿们来说，应该还是完全没有难度的。好的，至此我们的单列集合之List接口就算是全部搞定了。下一小节我们将开始进入set集合的内容，大家不见不散😆。感谢阅读！

        System.out.println("END----------------------------------------------------------");